Rust で 三角形 を書く
https://scrapbox.io/files/6855768fb9a11cdf0a6d0d5d.png
方針
1. 3頂点を$ y座標値に基づいてソートする
2. $ y方向を線形走査する形で、三角形内部を塗りつぶす
ある$ y = y_0における三角形の端点がどこにあるかを調べたい 3点の頂点から与えられた点をベースに示す
https://scrapbox.io/files/66ee77e44bc5c1001cea3093.png
記号の定義
三角形を包む最小のAABB矩形を考える。($ (x_{min}, y_{min}), (x_{max}, y_{max}))
三角形を構成する点を$ p_0 = (x_0, y_0), p_1 = (x_1, y_1), p_2 = (x_2, y_2)とする。
上図(上向き正)において、$ p_0, p_1, p_2の順で徐々にy値が大きくなっていくことを仮定する。
for $ y \in \lbrack y_{min}, y_{max}\rbrack:
i. ある$ y 座標値において三角形が占めている区間$ \lbrack x_{l}, x_{r} \rbrackがどこにあるか？ （後述。GPUで動かす場合、ここは$ x_{min}, x_{max}としてよい）
ii. 区間$ \lbrack x_{l}, x_{r} \rbrackの中にある点$ p = (x_p, y_p)を塗る。
これは$ pを$ p_0, p_1, p_2を基底として$ p = w_0 p_0 + w_1 p_1 + w_2 p_2を表すものである。
$ w_0, w_1, w_2 \in \lbrack 0, 1 \rbrackであれば、$ pは三角形内部に存在する。
ほか、$ p_1 - p_0などの辺ベクトルとベクトル$ p- p_0の外積をとっても内部にあるかどうかを判定できる。
3点からなる三角形の面積は$ A_{012} = (p_1 - p_0) \times (p_2 - p_0)で求められる。 従って$ w_0 = A_{12p} / A_{012}, w_1 = A_{02p} / A_{012}, w_2 = A_{01p} / A_{012}
それぞれの点に属性$ C_0, C_1, C_2が割り当てられている場合
点$ pの属性値$ C_p = w_0 C_0 + w_1 C_1 + w_2 C_2として補間できる code:canvas/triangle.rs
pub fn draw_triangle(
&mut self,
) {
// y基準でソート
let bound_x = ClosedInterval::between(0,(self.width-1) as i32);
let bound_y = ClosedInterval::between(0,(self.height-1) as i32);
let range_y = ClosedInterval::range(points.map(|p| p.y.clone()));
let lines = [
Line::new(bottom, middle),
Line::new(middle, top),
Line::new(bottom, top),
];
let inv_abc = 1./(area(&points0, &points1, &points2) as f64); for y in &range_y.and(&bound_y) {
let edge = if y < middle.y { &lines0 } else { &lines1 }; let i_edge1 = lines2.across_y(y); let i_edge2 = edge.across_y(y);
let segment = (i_edge1.or(i_edge2)).and(&bound_x);
for x in &segment {
let p = Point2{x, y};
let w0 = area(&points1, &points2, &p) * inv_abc; let w1 = area(&points2, &points0, &p) * inv_abc; let w2 = area(&points0, &points1, &p) * inv_abc; self.draw_pixel(&p,&(w0*&color0 + w1 * &color1 + w2 * &color2)); }
}
ある$ y 座標値において三角形が占めている区間$ \lbrack x_{l}, x_{r} \rbrackがどこにあるか？ 辺$ p_0p_1をとり、$ y = kとの交点を調べてみる。
辺は$ t(p_1 - p_0) + p_0; t\in\lbrack 0, 1 \rbrackとして表せる。
従って、$ \frac{k - x_0}{y_1 - y_0} = tと求められるため、これで$ x = t(x_1 - x_0) + x_0を計算すれば良い。
$ y = k, y = k+1の場合をそれぞれ調べれば、$ \{x_l, x_r\}が得られる
この$ x_l, x_rを四捨五入整数除算によって求めることで誤差を心配することなく整数に切り落とせる。 ❗️ ピクセルのどこを中心とするかによって計算が変わる点に注意
$ y_1 = y_0の場合
$ y = kなら$ \lbrack x_{min}, x_{max} \rbrack
そうでなければ$ \emptyとすればいい。
実装例
code:canvas/line.rs
fn round_div(n:i64, d:i64) -> i32 {
if d < 0 {
round_div(-n, -d)
} else if n >= 0 {
((n + d/2) / d) as i32
} else {
-((-n + d/2) / d) as i32
}
}
code:canvas/line.rs
impl Line {
pub fn across_y(&self, y:i32) -> ClosedInterval {
if self.p1.y == self.p2.y {
return
if self.p1.y == 0 { ClosedInterval::between(self.p1.x, self.p2.x) }
else { ClosedInterval::empty() }
}
let delta = self.delta();
let delta_x = delta.x as i64;
let delta_y = delta.y as i64;
let y_y1 = (y - self.p1.y) as i64;
let x0 = self.p1.x + round_div(delta_x*y_y1, delta_y);
let x1 = self.p1.x + round_div(delta_x*(y_y1+1), delta_y);
ClosedInterval::between(x0, x1)
}
}